package 链表题目;

import 链表题目.model.ListNode;

import java.util.Stack;


//两数相加 II
//https://leetcode.cn/problems/add-two-numbers-ii/description/
class 两数相加2 {
    // 我的栈解法
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();
        while (l1 != null) {
            stack1.push(l1);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2);
            l2 = l2.next;
        }
        int addNum = 0;
        ListNode ans = new ListNode(0, null);
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            ListNode one = stack1.pop();
            ListNode two = stack2.pop();
            int sum = addNum + one.val + two.val;
            addNum = sum / 10;
            ans.next = new ListNode(sum % 10, ans.next);
        }
        if (stack1.isEmpty() && stack2.isEmpty() && addNum != 0) {
            ans.next = new ListNode(addNum, ans.next);
        }
        if (!stack1.isEmpty()) {
            getAddNum(stack1, addNum, ans);
        }
        if (!stack2.isEmpty()) {
            getAddNum(stack2, addNum, ans);
        }
        return ans.next;
    }

    private void getAddNum(Stack<ListNode> stack, int addNum, ListNode ans) {
        while (!stack.isEmpty()) {
            ListNode one = stack.pop();
            int sum = addNum + one.val;
            addNum = sum / 10;
            ans.next = new ListNode(sum % 10, ans.next);
        }
        if (addNum != 0) {
            ans.next = new ListNode(addNum, ans.next);
        }
    }

    // 试试递归-没写出来
//    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        ListNode ans = new ListNode(0, null);
//        int addNum = dfs(l1, l2, ans);
//        if (addNum != 0) {
//            ans.next = new ListNode(addNum, ans.next);
//        }
//        return ans.next;
//    }
//
//    private int dfs(ListNode l1, ListNode l2, ListNode ans) {
//        int addNum = 0;
//        if (l1.next != null || l2.next != null) {
//            if (l1.next != null && l2.next == null) {
//                addNum = dfs(l1.next, l2, ans);
//            } else if (l1.next == null && l2.next != null) {
//                addNum = dfs(l1, l2.next, ans);
//            } else {
//                addNum = dfs(l1.next, l2.next, ans);
//            }
//        }
//        int sum = l1.val + l2.val + addNum;
//        ans.next = new ListNode(sum % 10, ans.next);
//        return sum / 10;
//    }

//    public static void main(String[] args) {
//        ListNode tow5 = new ListNode(9, null);
//        ListNode tow4 = new ListNode(6, null);
//        ListNode tow3 = new ListNode(4, null);
//        ListNode tow2 = new ListNode(6, tow3);
//        ListNode tow1 = new ListNode(5, tow2);
//        ListNode one4 = new ListNode(3, null);
//        ListNode one3 = new ListNode(4, one4);
//        ListNode one2 = new ListNode(2, one3);
//        ListNode one1 = new ListNode(7, one2);
//        ListNode listNode = new AddTwoNumbers2().addTwoNumbers(one1, tow1);
//        System.out.println(listNode);
//    }
}
